#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <unordered_map>
#include <string>

using namespace std;

struct Edge {
    string dest;
    int weight;
};

struct Node {
    string name;
    vector<Edge> edges;
};

struct Graph {
    unordered_map<string, Node> nodes;
    
    void addEdge(string src, string dest, int weight) {
        nodes[src].edges.push_back({dest, weight});
        nodes[src].name = src;
        nodes[dest].name = dest;
    }
};

struct Compare {
    bool operator()(const pair<int, string>& a, const pair<int, string>& b) {
        return a.first > b.first;
    }
};

void dijkstra(Graph& graph, string start) {
    unordered_map<string, int> dist;
    unordered_map<string, string> prev;
    priority_queue<pair<int, string>, vector<pair<int, string>>, Compare> pq;

    for (auto& node : graph.nodes) {
        dist[node.first] = INT_MAX;
    }
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        string u = pq.top().second;
        pq.pop();

        for (Edge& edge : graph.nodes[u].edges) {
            string v = edge.dest;
            int alt = dist[u] + edge.weight;
            if (alt < dist[v]) {
                dist[v] = alt;
                prev[v] = u;
                pq.push({alt, v});
            }
        }
    }

    for (auto& d : dist) {
        if (d.second == INT_MAX) {
            cout << "从 " << start << " 到 " << d.first << " 没有路径" << endl;
        } else {
            cout << "从 " << start << " 到 " << d.first << " 的最短距离: " << d.second;
            cout << "，路径: ";
            vector<string> path;
            for (string at = d.first; at != ""; at = prev[at]) {
                path.push_back(at);
            }
            for (int i = path.size() - 1; i >= 0; i--) {
                cout << path[i];
                if (i != 0) cout << " -> ";
            }
            cout << endl;
        }
    }
}

int main() {
    Graph graph;
    cout << "输入图的边，格式为 源节点 目标节点 权重 (输入'end'结束):" << endl;
    
    while (true) {
        string src, dest;
        int weight;
        cin >> src;
        if (src == "end") break;
        cin >> dest >> weight;
        graph.addEdge(src, dest, weight);
    }

    string startNode;
    cout << "输入起始节点: ";
    cin >> startNode;

    if (graph.nodes.find(startNode) == graph.nodes.end()) {
        cout << "起始节点不存在" << endl;
        return 1;
    }

    dijkstra(graph, startNode);

    return 0;
}